/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package cs;

/**
 *
 * @author QuangHieu
 */

class khoi{
    int sd;
    char c1,c2,c3;
    khoi(){}
    khoi(int sd1, char cc1, char cc2, char cc3){
        sd=sd1; c1=cc1; c2=cc2; c3=cc3;
    }
}

class StackHN{
    khoi []a;
    int top;
    final int maxSize=1000;
    StackHN(){
        a=new khoi[maxSize+1];
        top=0;
    }

    boolean Emptys(){
        return top==0;
    }

    void Pushs(khoi x){
        if(top==maxSize)
            System.out.print("\nStack day!");
        else a[++top]=x;
    }

    khoi Pops(){
        khoi x=new khoi();
        if(top==0)
            System.out.print("\nStack rong!");
        else x=a[top--];
        return x;
    }
}

public class ThapHN {
    void HN(int sd, char a, char b, char c){
        if(sd==1)
            System.out.print("\nChuyen 1 dia tu "+ a + " sang "+ c);
        else{
            HN(sd-1,a,c,b);
            HN(1,a,b,c);
            HN(sd-1,b,a,c);
        }
    }

    void HN1(int sd,char c1, char c2, char c3){
        khoi x,z;
        x=new khoi(sd,c1,c2,c3);
        StackHN s=new StackHN();
        s.Pushs(x);
        while(!s.Emptys()){
            z=s.Pops();
            if(z.sd==1)
                System.out.print("\nChuyen tu "+ z.c1+" sang "+ z.c3);
            else{
                x=new khoi(z.sd-1, z.c2 , z.c1, z.c3);      s.Pushs(x);
                x=new khoi(1, z.c1 , z.c2, z.c3);           s.Pushs(x);
                x=new khoi(z.sd-1 , z.c1, z.c3, z.c2);      s.Pushs(x);
            }
        }
    }

    public static void main(String agrs[]){
        int n=3;
        ThapHN tn=new ThapHN();
        tn.HN(n, 'a', 'b', 'c');
        tn.HN1(n, 'a', 'b', 'c');
    }
}
